/*
 * Copyright (c) 2008, Justin Choy
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 * 
 * 2) Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 * 
 * 3) Neither the name of the owner nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
package data;

import error.*;

/**
 * A array class that stays sorted.
 * 
 * @author jchoy
 */
public class OrderedArray extends Array {

    /**
     * Constructor
     */
    public OrderedArray() {
    }            

    public static void main( String args[] ) {
        try {
            
            OrderedArray arr = new OrderedArray();
            
            arr.addValue(00);
            arr.addValue(99);
            arr.addValue(33);
            arr.addValue(55);
            arr.addValue(74);
            arr.addValue(12);
            arr.addValue(78);
            arr.addValue(39);
            arr.addValue(81);
            arr.addValue(22);
            arr.addValue(43);
            
            System.out.println( arr.getString() );
            int index = -1;
            
            try {
                index = arr.binarySearch( 22 );
            } catch (InvalidValueException e) {
                throw new ProgrammingErrorException( "Arrray did not find" +
                        " a value I inserted");
            }
            
            System.out.println( "Found 22 at index " 
                    + Integer.toString(index) + ".");
            
            try {
                index = arr.binarySearch( 11 );
            } catch (InvalidValueException e) {
                System.out.println( "Could not find 11 in array.");
            }
            
            try {
                System.out.println("Deleting 81 & 39.");
                arr.deleteValue(81);
                arr.deleteValue(39);
            } catch (InvalidValueException e) {
                throw new ProgrammingErrorException( "Arrray did not find" +
                " a value I inserted");
            }
            
            System.out.println( arr.getString() );
            
        } catch (ProgrammingErrorException e) {
            System.out.println( e.getMessage() );
        } catch (OutOfMemoryException e) {
            System.out.println(e.getMessage());
        }
        
    }
    
    /**
     * Inserts a value into the array
     * 
     * @param value The value to insert
     * @throws ProgrammingErrorException
     * @throws OutOfMemoryException 
     */
    public void addValue( long value ) 
    throws ProgrammingErrorException, OutOfMemoryException {
        
        /* Find the first value which is greater than the value we want
         * to insert
         */
        int i = 0;        
        for ( i = 0; i < getNumElements(); i++ ) {
            if ( array[i] > value ) {
                break;
            }
        }
            
        /* Insert the value at the index where we found the first greater value
         * than value and shift everything down one 
         */
        long temp = 0;
        while ( i < getNumElements() ) {
            temp = array[i];
            array[i++] = value;
            value = temp;
        }
        
        /* Lastly, append the last value to the array
         */
        super.addValue(value);
    }
    
    /**
     * Finds if the array includes searchValue using a binary search
     * 
     * @param searchValue The value we are trying to find
     * @throws InvalidValueException if value not found
     */
    public int binarySearch( long searchValue ) throws InvalidValueException {
        boolean isFound = false;
        int lowIndex = 0;
        int highIndex = getNumElements() - 1;
        int middleIndex = 0;
        
        while ( lowIndex <= highIndex ) {
            
            /* Set the middle index to the middle of low and high */
            middleIndex = ( lowIndex + highIndex ) >>> 1;
            long midVal = array[middleIndex];
            
            /* If the value is lower, we move our low index to 1 greater than
             * middle index
             */
            if ( midVal < searchValue ) {
                lowIndex = middleIndex + 1;
                
            /* If the value is highed, we set our high index to 1 less than
             * middle index
             */
            } else if ( midVal > searchValue ) {
                highIndex = middleIndex - 1;
                
            /* Else, we have found are value */
            } else {
                isFound = true;
                break;
            }
        }
        
        /* If we can't find it, throw and exception */
        if ( isFound == false ) {
            throw new InvalidValueException(Severity.NON_FATAL);
        }
        
        return middleIndex;
    }

}
